package com.aiguigu.sort;

public class ShellSort {
    public static void main(String[] args) {
        int temp;
        int arr[] = {10,14,-1,5,6,55,47};
        for (int gap = arr.length/2 ; gap>0; gap/=2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i-gap; j >=0; j-=gap) {
                    if (arr[j]>arr[j+gap]){
                        temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }
        }
        for (int i : arr) {
            System.out.print(i+" ");
        }
        ShellSort2(arr);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }
    public static void ShellSort2(int [] arr){
          for (int gap = arr.length/2;gap>0;gap/=2){
              for (int i = gap; i <arr.length ; i++) {
                  int j = i;
                  int temp = arr[j];
                  if (arr[j]<arr[j-gap]){
                      while (j>=0&&temp<arr[j-gap]){
                          arr[j] = arr[j-gap];
                          j-=gap;
                      }
                  }
                  arr[j] = temp;
              }
          }
    }
}
